package com.study.lu;

public class 找朋友 {

    /**
     * 给定一些人，并把这些人际关系告诉你，求这些人能分成几个朋友圈
     * 规则如下 如果a和b是朋友， 那么 ab是一个朋友圈，如果 a和b是朋友。b和c是朋友。a和c不是直接朋友，但是是间接朋友。那么abc也算是一个朋友圈
     * 如果 a和b之间不是朋友，也不是间接朋友，那么a b各属于不同的朋友圈
     * 入参如下 给定一个 n*n的二位数组。第一维是各个人，第二维是与其他人之间的关系。是直接朋友值为1 不是值为0
     * 如下举例
     * a ：1,1,0,0   a与b是直接朋友
     * b : 1,1,1,0   b与a。c是直接朋友
     * c : 0,1,1,0   c与b是直接朋友
     * d : 0,0,0,1   d 与任何人都不是直接盆友，。
     *
     * @param args
     */
    public static void main(String[] args) {
        int[][] friends = new int[][]{
                {1, 1, 0, 0},
                {1, 1, 1, 0},
                {0, 1, 1, 0},
                {0, 0, 0, 1},
        };

        int[][] friends2 = new int[][]{
                {1, 0, 0, 0},
                {0, 1, 0, 0},
                {0, 0, 1, 0},
                {0, 0, 0, 1},
        };

        // 深度优先
        System.out.println(dfs(friends));
        System.out.println(dfs(friends2));

        // 广度优先


    }

    private static int dfs(int[][] persons) {
        // 一共有多少个人
        int personSize = persons.length;
        // 谁已经找到朋友了
        boolean[] foundFriend = new boolean[personSize];
        // 朋友圈的个数
        int friendsSize = 0;
        for (int personNo1 = 0; personNo1 < personSize; personNo1++) {
            // 如果这个人还没找到朋友则进行深度遍历
            if (!foundFriend[personNo1]) {
                doDfs(personNo1, personSize, foundFriend, persons);
                friendsSize++;
            }
        }

        return friendsSize;
    }

    private static void doDfs(int personNo1, int personSize, boolean[] foundFriend, int[][] persons) {
        // 第一次说明
        // 那么这里就进行 {1, 1, 0, 0}, 遍历，1代表是直接朋友，0则反之
        for (int personNo2 = 0; personNo2 < personSize; personNo2++) {
            // 如果这个人与张三是直接朋友，那么就要找到张三的其他朋友。直到没找到为止或者全部找完
            if (!foundFriend[personNo2] && persons[personNo1][personNo2] == 1) {
                // 先标记 已找到，这样就不会重复找了
                foundFriend[personNo2] = true;
                // 递归查找
                doDfs(personNo2, personSize, foundFriend, persons);

            }
        }
    }
}
